package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-23
 * Time: 9:05
 */
public class TestDemo2 {


    public static int longestPalindromeSubseq(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        //[L......R]
        char[] str = s.toCharArray();
        return process(str,0,s.length()-1);
    }

    public static int process(char[] str,int L,int R){
         if(L==R){
             return 1;
         } else if(L==R-1){
             return str[L] == str[R] ? 2 : 1;
         }else {
             //L是 R不是
             int p1 = process(str,L,R-1);
             //L不是 R是
             int p2 = process(str,L+1,R);
             //L是 R是
             int p3 = process(str,L+1,R-1);
             //L不是 R不是
             int p4 = str[L] == str[R] ? 2+ process(str,L+1,R-1) :0;
             return  Math.max(Math.max(p1,p2),Math.max(p3,p4));
         }
    }

    public static int longestPalindromeSubseq1(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        //[L......R]
        char[] str = s.toCharArray();
        return process1(str,0,s.length()-1);
    }

    public static int process1(char[] str,int L,int R){
        if(L==R){
            return 1;
        } else if(L==R-1){
            return str[L] == str[R] ? 2 : 1;
        }else {
            //L是 R不是
            int p1 = process(str,L,R-1);
            //L不是 R是
            int p2 = process(str,L+1,R);
            //L不是 R不是
            int p3 = str[L] == str[R] ? 2+ process(str,L+1,R-1) :0;
            return  Math.max(Math.max(p1,p2),p3);
        }
    }

//    public static int longestPalindromeSubseq2(String s) {
//        if(s==null||s.length()==0){
//            return 0;
//        }
//        //[L......R]
//
//        return process2(str,0,s.length()-1);
//    }

    public static int longestPalindromeSubseq2(String s){
        char[] str = s.toCharArray();
        int N = str.length;
        int[][] dp = new int[N][N];
        dp[N-1][N-1] = 1;
        for(int i = 0;i<N;++i){
            dp[i][i] = 1;
            dp[i][i+1] = str[i]==str[i+1] ?2 :1;
        }

        for(int L = N-2;L>=0;L--){
            for(int R = L+1;R<N;++R){
                int p1 = dp[L][R-1];
                //L不是 R是
                int p2 = dp[L+1][R];
                //L不是 R不是
                int p3 = str[L] == str[R] ? 2+ dp[L+1][R-1] :0;
                dp[L][R] = Math.max(Math.max(p1,p2),p3);
            }
        }
        return dp[0][N-1];
    }




    public static void main(String[] args) {

    }

}
